package com.Sep_Seven;

import com.Sep_Six.Solution222;

/**
 * 110. 平衡二叉树
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 *
 * 本题中，一棵高度平衡二叉树定义为：
 *
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 */

public class Solution110 {

    /**
     * 进行递归，比较左右子树的最大深度，是否<=1，进行平衡树判断
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return dfs(root)>=0;
    }

    public int dfs(TreeNode root){
        if (root==null) return 0;
        int leftDepth=dfs(root.left),rightDepth=dfs(root.right);
        if (leftDepth>=0&&rightDepth>=0&&Math.abs(leftDepth-rightDepth)<=1)
        {
            return Math.max(leftDepth,rightDepth)+1;
        }else
        {
            return -1;
        }
    }

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
